package com.jia.leetCode;

public class Pro0221 {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[][] dp = new int[rows][cols];

        int max = 0;
        for(int r = 0; r < rows; r++) {
            for(int c = 0; c < cols; c++) {
                if(r == 0 || c == 0) {
                    dp[r][c] = matrix[r][c]- '0';
                }else if(matrix[r][c] == '1') {
                    if(dp[r-1][c-1] != 0 ) {
                        int subsquraeLen = (int) Math.sqrt(dp[r-1][c-1]);
                        boolean isAllOne = true;
                        int k = 1;
                        for(; k <= subsquraeLen; k++) {
                            if(matrix[r][c-k] != '1' || matrix[r -k][c] != '1') {
                                isAllOne = false;
                                break;
                            }
                        }
                        dp[r][c] = isAllOne? (subsquraeLen + 1)*(subsquraeLen + 1) : k * k;
                    }else {
                        dp[r][c] = 1;
                    }
                }
                max = Math.max(max, dp[r][c]);
            }
        }
        return max;
    }

    public static void main(String[] args) {
        Pro0221 pro0221 = new Pro0221();
        char[][] matrix = {{'1','0','1','0'},{'1','0','1','1'},{'1','0','1','1'},{'1','1','1','1'}};
        System.out.println(pro0221.maximalSquare(matrix));;
    }
}
